//
//  PlanHot100.swift
//  SFQuestion
//
//  Created by liusr on 2024/11/10.
//

import Foundation
//2024年11月再做一次

// 今天这个写法 明天那个写法不看就往，复习 以这个为主吧，和力扣记录差不多

// 25年再做一遍

class PlanHot100 {
    
    
    //MARK: 双指针
    /**
     42.接雨水
     给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     
     核心就是求i处能达到的最大高度。它由左侧最大高度和右侧最大高度决定。
     力扣视频解析，前部分直观做法好理解。
     力扣解析有一部分不好理解，看下gpt和labuladong解析一致
     
     注：单调栈思路也可以理解下
     
     GPT双指针思路解释
     
     1.    两侧最高柱子决定当前位置的水位高度：
     •    左指针 left 处的水量由 leftMax - height[left] 决定；
     •    右指针 right 处的水量由 rightMax - height[right] 决定。
     2.    选择限制条件：
     •    如果 leftMax <= rightMax，说明当前的水位高度只能由左侧控制，因为右侧柱子不可能限制得更低，所以移动左指针。
     •    反之，如果 rightMax < leftMax，水位高度由右侧控制，移动右指针。
     3.    左右收缩：
     •    每次移动一个指针并更新相应的最高柱子（leftMax 或 rightMax）。
     •    累加当前柱子能接的水量。
     
     为什么这样理解更直观？
     
     1.    用 「两侧最高柱子」限制 的角度，不需要直接比较 height[left] 和 height[right]，更容易看出是谁在限制水量。
     2.    通过 leftMax 和 rightMax 的比较决定移动哪一侧的指针，逻辑清晰且易于实现。
     
     时间与空间复杂度
     
     •    时间复杂度：O(n)，每个元素最多被访问一次。
     •    空间复杂度：O(1)，只用了常量空间。
     */
    //我们要求出每一个位置的高度，left right肯定都要走一遍
    func trap(_ height: [Int]) -> Int {
        guard height.count > 2 else { return 0 }
        
        var left = 0                      // 左指针
        var right = height.count - 1      // 右指针
        var leftMax = height[left]        // 左侧的最高柱子
        var rightMax = height[right]      // 右侧的最高柱子
        var waterTrapped = 0              // 累计的雨水量
        
        while left <= right {
            if leftMax <= rightMax {//将相等合并了
                // 由左侧最大高度限制
                if height[left] < leftMax {
                    waterTrapped += leftMax - height[left] // 当前柱子能接的水量
                } else {
                    leftMax = height[left] // 更新左侧最高柱子
                }
                left += 1 // 移动左指针
            } else {
                // 由右侧最大高度限制
                if height[right] < rightMax {
                    waterTrapped += rightMax - height[right] // 当前柱子能接的水量
                } else {
                    rightMax = height[right] // 更新右侧最高柱子
                }
                right -= 1 // 移动右指针
            }
        }
        
        return waterTrapped
    }
    
    
    //MARK: 贪心算法
    //MARK: 45.跳跃游戏2
    /**
     给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
     
     每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
     
     0 <= j <= nums[i]
     i + j < n
     返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
     
     题目保证可以到达 nums[n-1]
     
     题解：
     [2,3,1,2,4,2,3]
     在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。
     
     在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。
     
     作者：力扣官方题解
     链接：https://leetcode.cn/problems/jump-game-ii/solutions/230241/tiao-yue-you-xi-ii-by-leetcode-solution/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    func jump(_ nums: [Int]) -> Int {
        
        let length = nums.count
        var steps = 0
        var maxPosition = 0
        var end = 0
        //遍历可以找到最大跳的位置，边界其实就代表这个范围内都是一条可以完成的，每到一个边界就是说必须再跳一下了。
        for i in 0..<length-1 {
            maxPosition = max(maxPosition, i + nums[i])
            if i == end {
                end = maxPosition
                steps += 1
            }
            print("maxPosition:\(maxPosition)")
            print("end:\(end)")
            print("steps:\(steps)")
        }
        return steps
    }
    
    //MARK: 树
    
    /**
     概念：
     树的高度，是根节点到叶子节点最长路径边数；树的深度和高度是一个概念。
     节点高度，该节点到其最深叶子节点的最长路径的边数。叶子节点的高度是0
     节点深度，根节点到此节点路径的边数
     
     
     
     */
    
    /**
     543. 二叉树的直径
     给你一棵二叉树的根节点，返回该树的 直径 。

     二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

     两节点之间路径的 长度 由它们之间边数表示。
     */
    /**
     我的解析：
     直径:一个节点a到另一个节点b有着最长的路径的话，我们可以认为是他俩的公共父节点c 的左右子树深度
     
     */
    var diameter = 0
    func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
        diameterDepth(root)
        return diameter
    }
    //思路相似，在dfs中针对题目意思做一些逻辑处理
    //这个方法求节点的高度,或者说以此节点为根节点子树的深度。只是概念问题
    func diameterDepth(_ root: TreeNode?) -> Int {
        if root == nil {
            return 0
        }
        let L = diameterDepth(root?.left)
        let R = diameterDepth(root?.right)
        //在遍历每个节点的高度过程中 我们记下这个值 并且一直取最大的
        diameter = max(diameter, L + R)
        //注意加上自己这个节点
        return max(L, R) + 1
    }
    
    //MARK: 108将有序数组转换为二叉搜索树
    /*
     取中间值
     */
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
        return sortedArrayToBSTHelper(nums, 0, nums.count - 1)
    }
    
    func sortedArrayToBSTHelper(_ nums: [Int], _ left: Int, _ right: Int) -> TreeNode? {
        //两层判断 左<右
        //越界
        if left > right {
            return nil
        }
        let mid = (left + right) / 2
        if mid < 0 || mid >= nums.count {
            return nil
        }
        let node = TreeNode(nums[mid])
        node.left = sortedArrayToBSTHelper(nums, left, mid - 1)
        node.right = sortedArrayToBSTHelper(nums, mid + 1, right)
        return node
    }
    
    /**
     102. 二叉树的层序遍历
     给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     */
    //层序遍历利用队列，还有一些题就是层序遍历的变种，改变入队出队的逻辑即可
    //搜索项目中："每层打印一行"有几个变种
    func levelOrder(_ root: TreeNode?) -> [[Int]] {
        //这个函数要求是一层的数据放在一起返回,那就不能放在一个数组了
        var res = Array<Array<Int>>()
        var queue = Array<TreeNode>()
        if let root {
            queue.append(root)
        }
        while queue.isEmpty == false {
            
            let node = queue.removeFirst()
        }

        return res
    }
    
    /*
     98. 验证二叉搜索树
     
     根据二叉搜索树的特点
     
     一个节点 要大于左子树的最大值，小于右子树的最小值
     
     所以可以递归检查他的左子树检查右子树
     
     */
    
    func isValidBST(_ root: TreeNode?) -> Bool {
        // 一开始传入空 可以理解为无穷小和无穷大
        return isValidBSTHelp(root, leftValue: nil, rightValue: nil)
    }
    
    func isValidBSTHelp(_ root: TreeNode?, leftValue: Int?, rightValue: Int?) -> Bool {
        
        guard let node = root else { return true }
        // 节点的值要大于最小的 否则就不符合
        if let leftValue, node.val <= leftValue {
            return false
        }
        // 节点的值要小于最大的 否则就不符合
        if let rightValue, node.val >= rightValue {
            return false
        }
        // 对于左子树 最大的值就是自己，最小的值，不知道一开始是无穷小 默认透传 可以自己走两个分支
        // 对于右子树 最小的值是自己，最大的值 不知道一开始是无穷大
        var res = isValidBSTHelp(root?.left, leftValue: leftValue, rightValue: node.val) &&
        isValidBSTHelp(root?.right, leftValue: node.val, rightValue: rightValue)
        return res
    }
    
    /**
     
     114. 二叉树展开为链表
     
     给你二叉树的根结点 root ，请你将它展开为一个单链表：
     展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
     展开后的单链表应该与二叉树 先序遍历 顺序相同。
     
     我的思考：
     按照先序遍历顺序相同，使用递归，在遍历到每个节点的时候 处理左右子树指向。每一次递归函数把节点所属的树串成一个连
     */
    
    func flatten(_ root: TreeNode?) {
        flattenHelp(root)
    }
    
    func flattenHelp(_ root: TreeNode?) -> TreeNode? {
        
        guard let root = root else { return nil }
        
        //对于当前节点，最终左指针为空，右指针指向左子树的最终的节点，原右节点挂在左子树最后一个节点下
        //所以要先遍历左右子树
        let lastLeftNode = flattenHelp(root.left)
        let lastRightNode = flattenHelp(root.right)
        
        if let leftNode = root.left {
            //有左子树，说明可以 将右子树挂在左子树的单链上
            lastLeftNode?.right = root.right
            //我们递归修改的node的左右子树，node还是头部，这里右子树最终还是指向之前的左子树
            root.right = leftNode
            root.left = nil
        }
        
        // 返回什么 返回的是当前节点串成单链表后最后那个节点.
        return lastRightNode ?? lastLeftNode ?? root
    }
    
    
    /**
     105. 从前序与中序遍历序列构造二叉树
     
     给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     
            1
        2       3
     4    5   6    7
     
     pre根左右 1 2 4 5 3 6 7
     in 左根右 4 2 5 1 6 3 7
     
     1是第一个根节点  2是第二个根节点 遍历完
     
     前序遍历的每一个开头都可以作为根，中序遍历找到根的位置，这个位置的左边是左子树，右边是右子树 ，递归构建
     搜索buildTree函数有个使用数组遍历的方法 ，略显笨重
     */
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        
        //递归的过程要知道这次的root 每递归一次 就知道 当前的这个节点。
        //关键 每一次递归 传入的一定是个完整的子树
        //我们可以传入代表这个子树的索引
        
        // 建立索引 快速找到root所在的根位置
        var inorderDic = [Int: Int]()
        for (index, value) in inorder.enumerated() {
            inorderDic[value] = index
        }
        
        var preIndex = 0
        
        func buildTreeHelp(_ start: Int, _ end: Int) -> TreeNode? {
            if start > end {
                return nil
            }
            //判空
            let value = preorder[preIndex]
            preIndex += 1
            var root = TreeNode(value)
            if let rootInorderIndex = inorderDic[value] {
                root.left = buildTreeHelp(start, rootInorderIndex - 1)
                root.right = buildTreeHelp(rootInorderIndex + 1, end)
            }
            
            return root
        }
        
        return buildTreeHelp(0, preorder.count - 1)
            
    }
    
    /*
     437. 路径总和 III
     给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

     路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
      
     注：gpt对话分析
     使用前缀和，
     本题求的是 个数 个数 满足条件的个数，使用哈希表记录前缀和出现的次数
     
     思考为什么要初始化为0 ：1  根节点直接出发”的路径和恰好为 targetSum 的情况。
     在遍历历史上是否存在某个“旧的路径和”，它能让当前路径和减出 targetSum
     假设你在某条从根走到当前节点的路径上，当前路径和是：
     currSum = sum(root → ... → currentNode)
     现在你希望找一段路径和为 targetSum 的子路径。

     如果在之前某个祖先节点（记为节点 P），它的路径和是：prevSum = sum(root → ... → P)
     那么，P 到当前节点之间的路径和是：currSum - prevSum
     如果 currSum - prevSum == targetSum，就说明：从 P 的下一个节点（即 P 的子节点）到当前节点，这段路径和正好是 targetSum。
     
     
     “之前的前缀和” 是为了反推当前路径中是否有某一段路径等于 targetSum，路径起点确实是“那个之前的点之后的节点”，但用前缀和比较的是“那个之前的点的路径和”。
     所以反过来想  我们求的是前缀和是否匹配 不是求和加起来等于target 计算个数 没计算路径
     
     // currentSum是动态变化的 所以起始节点 也就不固定
     */
    var preFixSumDic: [Int: Int] = [0: 1]// 前缀和为 0 的路径初始出现一次，
    func pathSum(_ root: TreeNode?, _ targetSum: Int) -> Int {
        return pathSumHelp(root, targetSum, 0)
    }
    
    func pathSumHelp(_ root: TreeNode?, _ targetSum: Int, _ curentSum: Int) -> Int {
        guard let root = root else { return 0 }
        
        
        var curentSum = curentSum + root.val
        var prefixSum = curentSum - targetSum
        // 存在说明有个前缀和符合要求
        var count = preFixSumDic[prefixSum] ?? 0
        
        //更新当前路径和的计数 加上当前的一个点 curentSum是当前的前缀和
        preFixSumDic[curentSum, default: 0] += 1
        // 开始往下找
        count = count + pathSumHelp(root.left, targetSum, curentSum)
        count = count + pathSumHelp(root.right, targetSum, curentSum)
        // 回溯到当前节点 要把当前的前缀和撤销掉
        // 撤销它对前缀和计数的影响  确保每条路径是独立的，不污染其他路径的统计。
        preFixSumDic[curentSum]! -= 1
        
        return count
    }
    
    /**
     236. 二叉树的最近公共祖先
     
     */
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        if root == nil || root === p || root === q {
            return root //为空或者找到 提前返回 注意直接返回个root即可
        }
        
        // 如果不是那就找左右子树 递归找
        let left = lowestCommonAncestor(root?.left, p, q)
        let ritght = lowestCommonAncestor(root?.right, p, q)
        
        //如果左右都找到了 当前节点返回给最上面 他就是那个公共节点
        if let left, let ritght {
            return root
        }
        
        //否则 返回不为空的一侧 祖先就在某一侧
        if let left {
            return left
        }
        
        if let ritght {
            return ritght
        }
        
        return nil
    }
    
    /**
     19. 删除链表的倒数第 N 个结点
     https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
     给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     
     */
    
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
            //两个指针 一个先往前走n步 就行
            //找那个节点 容易 删除还是需要技巧的 比如只有一个节点
            var dummy = ListNode(-1)//弄个假的头
            dummy.next = head
            var p1:ListNode? = dummy//第二个从假头开始 直接删除自己的下一个
            var p2:ListNode? = head
            //注意判断停止的位置
            for i in 0..<n {
                p2 = p2?.next
            }
        
        // 实际上就是让p2提前和p1拉开n的间距，然后p1走到要删除的那个节点的前一个位置
        // 提前建立链表节点的这种关系，利用走到头判断nil的这种思路，而且刚好 有个假节点记录了上一个节点。好好体会
        // 一上来就判断是不是空 是不是第一个节点的思路不够丝滑
            //p1已经是从上一个节点开始走了
            while p2 != nil {
                p1 = p1?.next
                p2 = p2?.next
            }
            
            //p1就是倒数第n个节点 的上一个节点
            p1?.next = p1?.next?.next
            return dummy.next//返回真正的
        }
    
    /*
     35. 搜索插入位置
     给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

     请必须使用时间复杂度为 O(log n) 的算法。
     
     */
    
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        if nums.isEmpty {
            return 0
        }
        var left = 0
        var right = nums.count - 1
        while left <= right {
            let mid = left + (right - left) / 2
            if nums[mid] < target {
                left += 1
            } else if nums[mid] > target {
                right -= 1
            } else {
                left = mid
                break
            }
        }
        return left
    }
    
    
}
